import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/15 9:09
 * @description 排序 + 二分查找
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n =  nums.length;
        int left = 0, right = nums[n - 1] - nums[0];
        // 二分查找数对距离，在区间【0，max(nums) - min(nums)】之间
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            // 计算当前 <= mid 的数对有多少, 固定右端点，二分查找 大于等于 nums[j] - mid的最小值下标i
            for (int j = 0; j < n; j++) {
                int i = binarySearch(nums, j, nums[j] - mid);
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return left;
    }
    public int binarySearch(int[] nums, int end, int value) {
        int left = 0, right = end;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < value) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }
}
